package com.ww.springboot.boot.algorithm.dp.study;

import java.util.HashMap;
import java.util.Map;

/**
 * 描述：第 N 个泰波那契数  递归与动态规划区别:递归根据逻辑循环计算 动态规划:递推 -》使用缓存存储低位值 避免重复计算
 * <p>
 * T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
 *
 * @author wanwei
 * @since 2021-11-05 16:55
 */
public class TribonacciDemo1 {
    public static void main(String[] args) {
        System.out.println(tribonacci(25));
    }

    public static int tribonacci(int n) {
        int[] tmp = {0, 1, 1};
        for (int i = 3; i <= n; i++)
            tmp[i % 3] = tmp[0] + tmp[1] + tmp[2];
        return tmp[n % 3];
    }
}
